package fenzhi;

import utils.RandomArrCreator;

import java.util.Arrays;

public class QuickSort {
    public Integer[] arr;
    public void sort(Integer[] array) {
        if (array == null || array.length < 2) return;
        this.arr = array;
        for (int i = 0; i < 20; i++) {
            System.out.print(arr[i]+"_");
        }
        long begin = System.currentTimeMillis();
        sort(0,array.length);
        long time = System.currentTimeMillis() - begin;
        System.out.println("花费时间为："+time/1000.0+"s ");
        for (int i = 0; i < 20; i++) {
            System.out.print(arr[i]+"_");
        }
        long begin1 = System.currentTimeMillis();
        Arrays.sort(arr);
        long time1 = System.currentTimeMillis() - begin;
        System.out.println("花费时间为："+time1/1000.0+"s ");
        System.out.println("--------------");
        for (int i = 0; i < 20; i++) {
            System.out.print(arr[i]+"_");
        }
    }
    /**
     * 对 [begin, end) 范围的元素进行快速排序
     * @param begin
     * @param end
     */
    public void sort(int begin, int end) {
        if (end - begin < 2) return;
// 确定轴点位置 O(n)
        int mid = pivotIndex(begin, end);
// 对子序列进行快速排序
        sort(begin, mid);
        sort(mid + 1, end);
    }
    /**
     * 构造出 [begin, end) 范围的轴点元素
     * @return 轴点元素的最终位置
     */
    public int pivotIndex(int begin, int end) {
// 备份begin位置的元素
        Integer pivot = arr[begin];
// end指向最后一个元素
        end--;
        while (begin < end) {
            while (begin < end) {
                if (cmp(pivot, arr[end]) < 0) { // 右边元素 > 轴点元素
                    end--;
                } else { // 右边元素 <= 轴点元素
                    arr[begin++] = arr[end];
                    break;
                }
            }
            while (begin < end) {
                if (cmp(pivot, arr[begin]) > 0) { // 左边元素 < 轴点元素
                    begin++;
                } else { // 左边元素 >= 轴点元素
                    arr[end--] = arr[begin];
                    break;
                }
            }
        }
// 将轴点元素放入最终的位置
        arr[begin] = pivot;
// 返回轴点元素的位置
        return begin;
    }
    /*
     * 返回值等于0，代表 array[i1] == array[i2]
     * 返回值小于0，代表 array[i1] < array[i2]
     * 返回值大于0，代表 array[i1] > array[i2]
     */
    private int cmp(Integer i1, Integer i2) {
        return i1.compareTo(i2);
    }
    public static void main(String[] args) {
        new QuickSort().sort(RandomArrCreator.random(10000, 1, 1000));
    }
}
